package sort.exchange;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * 快速排序 是对冒泡排序的一种改进
 */
public class Quick {
    public static void main(String[] args) {
        int[] arr = {1,8,6,3,4,5,2,7,0,9};
//        int[] arr = new int[1000000];
//        for (int i = 0; i < 1000000; i++) {
//            //0-8000000
//            arr[i] = (int)(Math.random() * 1000000);
//        }
        System.out.println(arr.length);
        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, 20)));

        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
        String date1 = simpleDateFormat.format(date);
        System.out.println("排序前的时间=" + date1);
        quick(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(Arrays.copyOfRange(arr, 0, 20)));
        System.out.println("排序后的时间=" + simpleDateFormat.format(new Date()));
    }

    public static void quick(int[] arr, int low, int high) {
        if (low < high) {
            int pivotPos = partition(arr, low, high);//每一次排序
            quick(arr, low, pivotPos - 1);
            quick(arr, pivotPos + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];//支点、中心
        while (low < high) {//外层while循环：找到一次大值放左边以及一次小值放右边，进入下一次循环 || low == high退出循环
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];//a[low]的值作为支点已存。arr[high]被放在arr[low]后，可视为空
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        //low == high外层循环退出 此时【low/high位置】的左边都比支点大，右边都比支点小
        arr[low] = pivot;
        return low;//返回旧支点
    }
}
